package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 51. N 皇后
 * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * <p>
 * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * <p>
 * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：n = 4
 * 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * 解释：如上图所示，4 皇后问题存在两个不同的解法。
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：[["Q"]]
 * <p>
 * 链接：https://leetcode-cn.com/problems/n-queens/
 */
public class N皇后问题 {

    public static void main(String[] args) {
        System.out.println(initN(8));
    }


    public static List<List<String>> initN(int n) {
        char[][] sim = new char[n][n];
        int[][] sim1 = new int[n][n];
        List<List<String>> jieguo = new ArrayList<List<String>>();
        for (int i = 0; i < n; i++) {
            Arrays.fill(sim[i], '.');
            Arrays.fill(sim1[i], 0);
        }
        backtrack(0, n, sim, sim1, jieguo);
        System.out.println(jieguo.size());
        return jieguo;
    }

    /**
     * @param k      表示第几行
     * @param n      表示几皇后问题
     * @param sim    表示每个皇后的位置
     * @param sim1   表示第几个位置可以摆放
     * @param jieguo 存储每个解法的结果
     * @return
     */
    public static void backtrack(int k, int n, char[][] sim, int[][] sim1, List<List<String>> jieguo) {
        if (k == n) {
            List<String> str = new ArrayList<String>();
            for (int i = 0; i < n; i++) {
                str.add(String.valueOf(sim[i]));
            }
            jieguo.add(str);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (sim1[k][i] == 0) {
//                int[][] copy = sim1.clone();
                int[][] copy = copyErWeiArray(sim1);
                put_queue(sim1, k, i);
                sim[k][i] = 'Q';
                backtrack(k + 1, n, sim, sim1, jieguo);
                //  触发回溯的机值就是 没有执行上面的return;
                sim[k][i] = '.';
                sim1 = copy;
            }
        }

    }


    public static int[][] copyErWeiArray(int[][] sim1) {
        int[][] ints = new int[sim1.length][sim1.length];
        for (int i = 0; i < sim1.length; i++) {
            ints[i] = sim1[i].clone();
        }
        return ints;
    }


    public static void put_queue(int[][] array, int x, int y) {
        int[] dx = new int[]{-1, 1, 0, 0, -1, -1, 1, 1};
        int[] dy = new int[]{0, 0, -1, 1, -1, 1, -1, 1};
        for (int j = 0; j < dx.length; j++) {
            for (int i = 0; i < array.length; i++) {
                int xx = x + i * dx[j];
                int yy = y + i * dy[j];
                if (xx >= 0 && xx < array.length && yy >= 0 && yy < array.length) {
                    array[xx][yy] = 1;
                }
            }
        }
    }

}
